package Class022;

//lc493:重要翻转对
//https://leetcode.com/problems/reverse-pairs/description/
public class FlipPairs {
    public static void main(String[] args) {

    }

    public static int reversePairs(int[] nums) {
        return merge(nums);
    }

    public static int merge(int[] nums) {
        return myMerge(nums, 0, nums.length - 1);
    }

    public static int myMerge(int[] arr, int l, int r) {
        if(l == r) return 0;
        int m = l + ((r - l) >> 1);
        return myMerge(arr, l, m)
                + myMerge(arr, m + 1, r)
                + mergeProcess(arr, l, r, m);
    }

    public static int mergeProcess(int[] arr, int l, int r, int m) {
        int sum = 0;
        int res = 0;
        for(int lp = l, rp = m + 1; lp <= m; lp++) {
            while(rp <= r && arr[lp] > 2 * (long)arr[rp]) {
                sum++;
                rp++;
            }
            res += sum;
        }

        int[] help = new int[r - l + 1];
        int lp = l, rp = m + 1, index = 0;
        while(lp <= m && rp <= r) {
            help[index++] = arr[lp] <= arr[rp] ? arr[lp++] : arr[rp++];
        }
        while(lp <= m) {
            help[index++] = arr[lp++];
        }
        while(rp <= r) {
            help[index++] = arr[rp++];
        }

        for(int i = 0; i < help.length; i++) {
            arr[l + i] = help[i];
        }
        return res;
    }
}
